//
// Created by wzl on 2022/4/20.
//

#include <stack>
#include <queue>
#include "bitree.h"

Status InitBiTree(BiTree &T) { /* 操作结果: 构造空二叉树T */
    T = NULL;
    return OK;
}

void DestroyBiTree(BiTree &T) { /* 初始条件: 二叉树T存在。操作结果: 销毁线索二叉树T */
    if (T) /* 非空树 */
    {
        if (T->lchild) /* 有左孩子 */
            DestroyBiTree(T->lchild); /* 销毁左孩子子树 */
        if (T->rchild) /* 有右孩子 */
            DestroyBiTree(T->rchild); /* 销毁右孩子子树 */
        free(T); /* 释放根结点 */
        T = NULL; /* 空指针赋0 */
    }
}


Status CreateBiTree(BiTree &T) { /* 按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树T。变量Nil表示空（子）树。*/
    TElemType ch;
    scanf("%c", &ch);
    if (ch == Nil) /* 空 */
        T = NULL;
    else {
        T = (BiTNode *) malloc(sizeof(BiTNode));
        if (!T)
            exit(OVERFLOW);
        T->data = ch; /* 生成根结点 */
        CreateBiTree(T->lchild); /* 构造左子树 */
        CreateBiTree(T->rchild); /* 构造右子树 */
    }
    return OK;
}


Status BiTreeEmpty(BiTree T) { /* 初始条件: 二叉树T存在 */
    /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
    if (T)
        return FALSE;
    else
        return TRUE;
}


int BiTreeDepth(BiTree T) { /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
    int i = 0, j = 0;
    if (!T)
        return 0;
    if (T->lchild)
        i = BiTreeDepth(T->lchild);

    if (T->rchild)
        j = BiTreeDepth(T->rchild);

    return i > j ? i + 1 : j + 1;
}

int CountLeaf(BiTree bt) //求叶子结点数量
{
    return 0;
}

void PreOrderTraverse(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。 */
    /* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
    if (T) /* T不空 */
    {
        Visit(T->data); /* 先访问根结点 */
        PreOrderTraverse(T->lchild, Visit); /* 再先序遍历左子树 */
        PreOrderTraverse(T->rchild, Visit); /* 最后先序遍历右子树 */
    }
}

void InOrderTraverse(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */

}


void PostOrderTraverse(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */

}


void LevelOrderTraverse(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 层次遍历T,对每个结点调用函数Visit一次且仅一次 */

    if (T == nullptr) {
        return; // 处理空指针情况
    }

    std::queue<BiTNode *> q;
    q.push(T);

    while (!q.empty()) {
        BiTNode *node = q.front();
        q.pop();
        Visit(node->data); // 调用Visit函数

        if (node->lchild != nullptr) {
            q.push(node->lchild);
        }
        if (node->rchild != nullptr) {
            q.push(node->rchild);
        }
    }

}


void PreOrderTraverseNoRecursive(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 先序非递归遍历T,对每个结点调用函数Visit一次且仅一次 */
    if (T == nullptr || Visit == nullptr) {
        return; // 如果树为空或访问函数为空，直接返回
    }

    std::stack<BiTree> stack;
    BiTree current = T;

    while (current != nullptr || !stack.empty()) {
        if (current != nullptr) {
            Visit(current->data); // 访问当前节点
            stack.push(current);
            current = current->lchild; // 移动到左子节点
        }else {
            current = stack.top();
            stack.pop();
            current = current->rchild; // 移动到右子节点
        }
    }

}

void InOrderTraverseNoRecursive(BiTree T, void(*Visit)(TElemType)) { /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
    /* 操作结果: 中序非递归遍历T,对每个结点调用函数Visit一次且仅一次 */

}

void Exchange(BiTree T)   //交换所有结点的左右子树
{

}
